package leetcode.editor.cn.dsa13_mergesort;

import java.util.Arrays;

public class MergeSort {

    /**
     * 归并排序
     */
    public static int[] mergeSort(int[] arr) {
        // 结束条件：长度小于等于1，无需排序直接返回
        if (arr.length <= 1) return arr;
        // 分解：计算中间位置，分解为左右两部分
        int mid = arr.length / 2;
        // 求解：左半部分递归求解
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        left = mergeSort(left);
        // 求解：右半部分递归求解
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        right = mergeSort(right);
        // 合并：将两个排序后的数组合并为一个数组
        return merge(left, right);
    }
    // 合并两个有序数组
    private static int[] merge(int[] l, int[] r) {
        // 创建数组用于存放合并后的结果
        int[] result = new int[l.length + r.length];
        // 使用两个变量分别记录两个数组的当前位置
        int lIndex = 0, rIndex = 0;
        // 遍历两个数组每次找最小的放入结果数组中
        for (int i = 0; i < result.length; i++) {
            if (lIndex < l.length && rIndex < r.length) {
                // 两个数组都还有元素，则比较取较小的
                if (l[lIndex] <= r[rIndex]) {
                    result[i] = l[lIndex++];
                } else {
                    result[i] = r[rIndex];
                }
            // 如果其中一个为空则另一个依次复制到结果数组中
            } else if (lIndex < l.length) {
                result[i] = l[lIndex++];
            } else {
                result[i] = r[lIndex++];
            }
        }
        return result;
    }
}
